|
計算複雑性理論において、複雑性クラス E とは、決定性チューリング機械で 2O(n) の時間で解ける決定問題の集合である。これはすなわち、複雑性クラス DTIME(2O(n)) に等しい。 E は類似のクラス EXPTIME よりも理論上の重要性が低いとされる。それは、多項式時間多対一還元において閉じていないためである。 == 参考文献 == * E. Allender and M. Strauss. Measure on small complexity classes with applications for BPP, ''Proceedings of IEEE FOCS'94'', pp. 807-818, 1994. ECCC TR94-004 , DIMACS TR 94-18 . * R. Book. On languages accepted in polynomial time, ''SIAM Journal on Computing'' 1(4):281-287, 1972. * R. Book. Comparing complexity classes, ''Journal of Computer and System Sciences'' 3(9):213-229, 1974. * R. Impagliazzo and G. Tardos. Decision versus search problems in super-polynomial time, in ''Proceedings of IEEE FOCS 1989'', pp. 222-227, 1989. * O. Watanabe. Comparison of polynomial time completeness notions, ''Theoretical Computer Science'' 53:249-265, 1987. 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「E (計算複雑性理論)」の詳細全文を読む スポンサード リンク
|